/***************************************************************************
 * File name: q4.c
 *
 * Authors:  Tomer Filiba		Reuven Horon
 *           037013075			066729740
 *           sebulba@t2			sreuvenh@t2 
 *
 * Exercise #: 6
 * Question #: 4
 * Submission Date: 29/8/07
 **************************************************************************/

/*-------------------------------------------------------------------------
  Include files:
--------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>

/*=========================================================================
  Constants and definitions:
==========================================================================*/
#define DAYS_NUM	(9)
#define ORDERS_NUM	(5)
#define SUCCESS		(0)
#define FAILURE		(1)

typedef enum
{
	TRUE = (0 == 0),
	FALSE = (1 == 0)
} bool_t;

/*=========================================================================
  Forward declarations:
==========================================================================*/
int getNumTrucks();
int chooseOrders(int orderTrucks[ORDERS_NUM], int orderFrom[ORDERS_NUM], 
				int orderUntil[ORDERS_NUM], int orderAccept[ORDERS_NUM], 
				int numTrucks);
void printOrderAccept(int truckDays, int orderTrucks[ORDERS_NUM], 
                int orderFrom[ORDERS_NUM], int orderUntil[ORDERS_NUM], 
                int orderAccept[ORDERS_NUM]);
int choose_aux(int curr,
			   int days[DAYS_NUM],
			   int orderTrucks[ORDERS_NUM], 
			   int orderFrom[ORDERS_NUM], 
			   int orderUntil[ORDERS_NUM], 
			   int orderAccept[ORDERS_NUM]);


/*-------------------------------------------------------------------------
  The main program.

  The program deals with orders of trucks usage. It decides which orders 
  to accept and which to decline. 

  The details of each order are specified in the arrays orderTrucks (the 
  number of trucks requested for each order), orderFrom (the first day of 
  the time period requested for each order) and orderTo (the last day of 
  the time period requested for each order).

  The program maximizes the total number of truck days usage thought 
  all the time period (between day 0 to day DAYS_NUM-1), and prints its
  desicion details.
 -------------------------------------------------------------------------*/
int main() 
{
	int truckDays=0, numTrucks=0;
	int orderAccept[ORDERS_NUM] = {0};
	int orderTrucks[ORDERS_NUM] = {4, 4, 2, 3, 2};
	int orderFrom[ORDERS_NUM]   = {0, 1, 3, 5, 8};
	int orderUntil[ORDERS_NUM]  = {2, 5, 4, 6, 8};
	
	numTrucks = getNumTrucks();
	truckDays = chooseOrders(orderTrucks, orderFrom, orderUntil, orderAccept, numTrucks);
	printOrderAccept(truckDays, orderTrucks, orderFrom, orderUntil, orderAccept);
	
	return SUCCESS;
}

/*-------------------------------------------------------------------------
  reads the number of available trucks from the user

  parameters: none
  return value: number of trucks; on input error, terminates the program
 -------------------------------------------------------------------------*/
int getNumTrucks()
{
	int num = 0;
	printf("Enter number of trucks: ");
	if (scanf("%d", &num) != 1) {
		printf("Error: expected a number\n");
		exit(FAILURE);
	}
	if (num < 0) {
		printf("Error: number must be >= 0\n");
		exit(FAILURE);
	}
	return num;
}

/*-------------------------------------------------------------------------
  makes an optimal choice of the orders, so that the maximal number of
  truck days can be utilized

  Parameters:
  int truckDays               - the total truck days usage
  int orderTrucks[ORDERS_NUM] - orderTrucks[i] contains the amount of trucks 
                                requested by order i
  int orderFrom[ORDERS_NUM]   - orderFrom[i] contains the first day of the
                                time period requested by order i
  int orderUntil[ORDERS_NUM]     - orderTo[i] contains the last day of the
                                time period requested by order i
  int orderAccept[ORDERS_NUM] - orderAccept[i] contains 1 if order i was
                                accepted, and 0 if it was not
 
  return value: the maximal number of truck days
 -------------------------------------------------------------------------*/
int chooseOrders(int orderTrucks[ORDERS_NUM], 
				 int orderFrom[ORDERS_NUM], 
				 int orderUntil[ORDERS_NUM], 
				 int orderAccept[ORDERS_NUM],
				 int numTrucks)
{
	int i;
	int days[DAYS_NUM];
	
	/* init days array */
	for (i = 0; i < DAYS_NUM; i++) {
		days[i] = numTrucks;
	}
	
	/* recursively solve the problem */
	return choose_aux(0, days, orderTrucks, orderFrom, 
		orderUntil, orderAccept);
}

/*-------------------------------------------------------------------------
  helper function for chooseOrders, which uses backtracking to cover all
  the options of choosing orders, and makes the maximal choice each time

  Parameters:
  int curr                    - the index of the current order to process
  int days[DAYS_NUM]          - the number of available trucks for each day
  int orderTrucks[ORDERS_NUM] - orderTrucks[i] contains the amount of trucks 
                                requested by order i
  int orderFrom[ORDERS_NUM]   - orderFrom[i] contains the first day of the
                                time period requested by order i
  int orderUntil[ORDERS_NUM]     - orderTo[i] contains the last day of the
                                time period requested by order i
  int orderAccept[ORDERS_NUM] - orderAccept[i] contains 1 if order i was
                                accepted, and 0 if it was not
 
  return value: the maximal number of truck days
 -------------------------------------------------------------------------*/
int choose_aux(int curr,
			   int days[DAYS_NUM],
			   int orderTrucks[ORDERS_NUM], 
			   int orderFrom[ORDERS_NUM], 
			   int orderUntil[ORDERS_NUM], 
			   int orderAccept[ORDERS_NUM])
{
	int j, count, count2;
	int days2[DAYS_NUM], orderAccept2[ORDERS_NUM];
	bool_t can_use_curr = TRUE;
	
	if (curr >= ORDERS_NUM) {
		return 0;
	}
	
	/* see if we can use the current order */
	for (j = 0; j < DAYS_NUM; j++) {
		if (j >= orderFrom[curr] && j <= orderUntil[curr]) {
			days2[j] = days[j] - orderTrucks[curr];
			if (days2[j] < 0) {
				can_use_curr = FALSE;
				break;
			}
		}
		else {
			days2[j] = days[j];
		}
	}
	
	/* init temp array to hold the hypothetical choice, if we were 
	   to use the current order*/
	for (j = 0; j < ORDERS_NUM; j++) {
		orderAccept2[j] = orderAccept[j];
	}
	orderAccept2[curr] = 1;
	
	/* first try -- don't use the current order */
	count = choose_aux(curr + 1, days, orderTrucks, orderFrom, 
					   orderUntil, orderAccept);
	
	/* second try -- use current order if possible */
	if (can_use_curr) {
		count2 = orderTrucks[curr] * (orderUntil[curr] - orderFrom[curr] + 1);
		count2 += choose_aux(curr + 1, days2, orderTrucks, orderFrom, 
						     orderUntil, orderAccept2);
		/* now choose the maximal order */
		if (count2 > count) {
			count = count2;
			for (j = 0; j < ORDERS_NUM; j++) {
				orderAccept[j] = orderAccept2[j];
			}
		}
	}
	
	return count;
}


/*-------------------------------------------------------------------------
  Prints the orders accepted (with their details), the orders declined
  (with their details), and the number of truck days usage.

  Parameters:
  int truckDays               - the total truck days usage
  int orderTrucks[ORDERS_NUM] - orderTrucks[i] contains the amount of trucks 
                                requested by order i
  int orderFrom[ORDERS_NUM]   - orderFrom[i] contains the first day of the
                                time period requested by order i
  int orderUntil[ORDERS_NUM]     - orderTo[i] contains the last day of the
                                time period requested by order i
  int orderAccept[ORDERS_NUM] - orderAccept[i] contains 1 if order i was
                                accepted, and 0 if it was not

  Return value: void
 -------------------------------------------------------------------------*/
void printOrderAccept(int truckDays, 
					  int orderTrucks[ORDERS_NUM], 
					  int orderFrom[ORDERS_NUM], 
					  int orderUntil[ORDERS_NUM], 
					  int orderAccept[ORDERS_NUM])
{
	int i;
	printf("* There are %d truck days usage\n", truckDays);
	printf("* Orders accepted:\n");
	for (i=0; i<ORDERS_NUM; i++)
	{
		if (orderAccept[i])
		{
			printf("  \t%d: %d trucks, used in days [%d - %d]\n", 
				i, orderTrucks[i], orderFrom[i], orderUntil[i]);
		}
	}
	printf("* Orders declined:\n");
	for (i=0; i<ORDERS_NUM; i++)
	{
		if (!orderAccept[i])
		{
			printf("  \t%d: %d trucks, used in days [%d - %d]\n", 
				i, orderTrucks[i], orderFrom[i], orderUntil[i]);
		}
	}
}

/**************************************************************************
			                          End of file
***************************************************************************/
